package data_structure.mooc;

import java.util.Random;

public class MaxHeap<E extends Comparable<E>> {


    private Array<E>data;

    public MaxHeap(int capacity){
        data=new Array<E> (capacity);
    }

    public MaxHeap(){
        data = new Array<E> ();
    }

    public MaxHeap(E []arr){
        data = new Array<E> (arr);
        for(int i=parent (arr.length - 1);i>=0;i--){
            siftDown (i);
        }
    }

    public int getSize() {
        return data.getSize();
    }

    public boolean isEmpty() {
        return data.isEmpty ();
    }

    /**
     * 添加辅助私有方法
     */

    private int  parent(int index){

        if(index==0)throw new IllegalArgumentException ("index-0 is the root node");
        return (index-1)/2;
    }

    private int  leftChild(int index){

        return index*2+1;
    }

    private int  rightChild(int index){

        return index*2+2;
    }

    public void add(E e){
        data.addLast (e);
        siftUp(data.getSize ()-1);
    }

    private void siftUp(int k){
        //上浮
        while(k>0&&data.get (parent (k)).compareTo (data.get (k))<0){
            data.swap (parent(k),k);
            k=parent(k);
        }
    }

    public E replaceMax(E e){
        E temp=findMax ();
        data.set (e,0);
        siftDown (0);
        return temp;
    }

    public E findMax(){
        if(data.getSize () == 0)
            throw new IllegalArgumentException ("heap is null");
        return data.getFirst ();
    }

    public E extractMax(){
        E ret=findMax ();
        data.swap (0,data.getSize ()-1);
        data.removeLast ();
        siftDown(0);
        return ret;
    }

    private void siftDown(int k){
        //左孩子不为空时
        while(leftChild (k)<data.getSize ()){
            //找到左右孩子的最大值的下标，同父节点比较
            int i=leftChild(k);
            if(i+1<data.getSize ()&&data.get (i+1).compareTo (data.get (i))>0){
                i=i+1;
            }
            //符合最大堆数据分布，结束循环
            if(data.get(k).compareTo(data.get(i)) > 0)break;
            //交换
            data.swap (k,i);
            k=i;
        }
    }

    private static void test(String string,Integer[] arr){
        MaxHeap<Integer>heap;
        int n=100000;
        long start=System.nanoTime ();
        if(string.equals ("add")){
            for(int i = 0; i < n; i++){
                heap=new MaxHeap<> ();
                heap.add (arr[i]);
            }
        }else if (string.equals("heapify")){
            heap = new MaxHeap<> (arr);
        }
        long end=System.nanoTime ();
        System.out.println(string+"---"+"time:"+(end-start)/1000000000.0);
    }
    public static void main(String[] args) {
        Random random = new Random ();
        Integer[]arr1=new Integer[1000000];
        Integer[]arr2=new Integer[1000000];
        for (int i = 0; i < 1000000;i++){
            arr1[i]=random.nextInt(Integer.MAX_VALUE);
            arr2[i]=random.nextInt(Integer.MAX_VALUE);
        }
        test ("add",arr1);
        test ("heapify",arr2);
    }

}
